"""
1751. 最多可以参加的会议数目 II
困难
相关标签
premium lock icon
相关企业
提示
给你一个 events 数组，其中 events[i] = [startDayi, endDayi, valuei] ，表示第 i 个会议在 startDayi 天开始，第 endDayi 天结束，如果你参加这个会议，你能得到价值 valuei 。同时给你一个整数 k 表示你能参加的最多会议数目。

你同一时间只能参加一个会议。如果你选择参加某个会议，那么你必须 完整 地参加完这个会议。会议结束日期是包含在会议内的，也就是说你不能同时参加一个开始日期与另一个结束日期相同的两个会议。

请你返回能得到的会议价值 最大和 。



示例 1：



输入：events = [[1,2,4],[3,4,3],[2,3,1]], k = 2
输出：7
解释：选择绿色的活动会议 0 和 1，得到总价值和为 4 + 3 = 7 。
示例 2：



输入：events = [[1,2,4],[3,4,3],[2,3,10]], k = 2
输出：10
解释：参加会议 2 ，得到价值和为 10 。
你没法再参加别的会议了，因为跟会议 2 有重叠。你 不 需要参加满 k 个会议。
示例 3：



输入：events = [[1,1,1],[2,2,2],[3,3,3],[4,4,4]], k = 3
输出：9
解释：尽管会议互不重叠，你只能参加 3 个会议，所以选择价值最大的 3 个会议。


提示：

1 <= k <= events.length
1 <= k * events.length <= 106
1 <= startDayi <= endDayi <= 109
1 <= valuei <= 106
"""
from typing import List


class Solution:
    def maxValue(self, events: List[List[int]], k: int) -> int:

        pass
    def maxValue_test1(self, events: List[List[int]], k: int) -> int:
        """
        题目理解有误，未考虑k 这题是1235d的解法
        dp,根据结束时间，考虑选当前和不选当前的情况,
        定义数组三维数组cache[max(left)][i][2],以right作为索引，存储个二维数组，二维数组每一项为[left,价值]
        定义数组dp[],计算每项的最最优情况，条件表达式为
        对于cache[i],执行 max(dp[i-1],dp[cache[i][j1][0] - 1] + cache[i][j1][1],...dp[cache[i][jn][0] - 1] + cache[i][jn][1])
        同一天内有多个则同时计算max
        :param events:
        :param k:
        :return:
        """
        #右边界最大值
        max1 = max(e[1] for e in events )
        #先定义二维
        cache = [[] for _ in range(max1 + 1)]  # 每个元素是一个 list of [start, value]
        #二维每项是个数组
        for start, end, value in events:
            cache[end].append([start, value])

        dp = [0] * (max1+1)
        dp[0] = 0
        #状态转移
        for i in range(1,max1+1):
            if(cache[i] == []):
                dp[i] = dp[i-1]
            else:
                maxValue = dp[i - 1]
                list = cache[i]
                #i是left，j
                for left,value in list:
                    maxValue = max(maxValue,dp[left - 1] + value)
                dp[i] = maxValue
        return dp[max1]

if __name__ == '__main__':
    # print(Solution().maxValue([[1,2,4],[3,4,3],[2,3,1]],2))
    print(Solution().maxValue([[1,1,1],[2,2,2],[3,3,3],[4,4,4]],3))
